252C - Points on Line - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define INF 1000000007
#define INF_ll 1000000000000000007
#define ll long long
#define endl "\n"
#define uint unsigned long long 
#define unmp unordered_map
#define unst unordered_set
#define int long long 
#define f first
#define s second
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl
#define line cout << " " << endl
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define safai(...) Clearing_out(__VA_ARGS__)
template <typename A, typename B>
    string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
    string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
    string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
    return '"' + s + '"';
}
 
string to_string(char c) {
    string s;
    s += c;
    return s;
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(bool b) {
    return (b ? "1" : "0");
}
 
string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
        res += ", ";
    }
    first = false;
    res += to_string(v[i]);
    }
    res += "}";
    return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for (size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}
 
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
 
void Clearing_out() { return; }
 
template <typename Head, typename... Tail>
void Clearing_out(Head &H, Tail & ... T) {
    H.clear();
    Clearing_out(T...);
}

void time(){
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

void hi(){
    static int i=0;
    cerr << "Check Point : " << ++i << endl;
    return;
}
/***************************************************/


/////////////////////////////////////////////////////
int stoi1(string str){
    bool negative;
    if(str[0]=='-'){
        negative=true;
        str=str.substr(1);
    }
    else{
        negative=false;
    }
    int n=str.length();
    int number = 0;
    int pos = 1;
    for(int i=n-1;i>=0;i--){
        number = number + (str[i]-'0')*pos;
        pos=pos*10;
    }
    if(negative) number=-number;
    return number;
}

int power(int a,int n){
    int res = 1;
    while(n>0){
        if(n%2!=0){
            res = res*a;
            n--;
        }
        else if(n%2==0){
            a = a*a;
            n=n/2;
        }
    }
    return res;
}
/////////////////////////////////////////////////////



//DECLARE VARIABLE AND MAKE CHANGES AFTER HERE






signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    t=1;
    //cin >> t;
    while(t--){
        int n, d;
        cin >> n >> d;
        vector<int> v(n);
        for(int i = 0;i<n;i++){
            cin >> v[i];
        }
        int ans = 0;
        for(int i = 0;i<n;i++){
            int index = lower_bound(v.begin(), v.end(), v[i]+d) - v.begin();
            if(index==n){
                index = n-1;
            }
            else{
                if(v[index]>v[i]+d){
                    index--;
                }   
                else{

                }      
            }
            if(index<=i) continue;
            ans += ((index-i-1)*(index-i))/2;
        }
        cout << ans << endl;
    }
    time();
    return 0;
    
}